#include <iostream>
#include <vector>
using namespace std;

struct node
{
	int val;
	node *left;
	node *right;
	node(int v, node *l = NULL, node *r = NULL)
	{
		val = v;
		left = l;
		right = r;
	}
};

//print every route from root to leaf
void printtree(node *root, vector<node*> &V)
{
	if(root == NULL)
		return;	
	V.push_back(root);
	if(!root->left && !root->right)
	{
		for(int i=0; i<V.size(); i++)
			cout << V[i]->val;
		cout << endl;
	}		
	else
	{
		if(root->left)
			printtree(root->left, V);
		if(root->right)
			printtree(root->right, V);
	}
	V.pop_back();
}

void printtree2(node *root)
{
	vector<node*> V;
  node* p = root;
	while(p || V.size())
	{
		if(p)
		{
			V.push_back(p);
			V.push_back(NULL);
			if(p->right == NULL && p->left == NULL)
			{
				for(int i=0; i<V.size(); i++)
				{
					if(V[i])
						cout << V[i]->val;
				}
				cout << endl;
			}		
			p = p->left;
		}
		else
		{
			if(V[V.size()-1] == NULL)
			{
					V.pop_back();
					p = V[V.size()-1]->right;
			}
			else
				V.pop_back();	
		}
	}	
}

int main()
{
	node n4(4);
	node n5(5);
	node n6(6);
	node n7(7);
	node n2(2, &n4, &n5);
	node n3(3, &n6, &n7);
	node n1(1, &n2, &n3);	
	node n8(8);
	n7.left = &n8;
	cout << "==========================================" << endl;
	vector<node*> V1;
	printtree(&n1, V1);
	cout << "==========================================" << endl;
	printtree2(&n1);
	cout << "==========================================" << endl;
	vector<node*> V2;
	printtree(NULL, V2);
	cout << "==========================================" << endl;
	return 0;
}


